/*
 抽象数据类型：顺序存储的线性表
*/



/******************************引用部分******************************/
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#include "../StateCode.c"

/******************************定义部分******************************/
#define LIST_INIT_SIZE 10			//构造、初始化时默认的大小
#define LISTINCREMENT 10			//扩充列表时的增量

//定义数据元素
typedef struct Elem
{
	int number;						//存储数字
}ELEM;

//定义数据对象
struct ArrayList
{
	struct Elem* elem;				//数据内容
	int length;						//内容长度
	int listSize;					//列表容量
};

///////////定义操作
//构造一个空的线性表：无线性表，构造一个有的空的线性表
Status InitList(struct ArrayList* L)
{
	//动态申请List_Init_Size个Elem大小的空间，并将其赋予给L.elem
	L->elem = (struct Elem*)malloc(LIST_INIT_SIZE * sizeof(struct Elem));
	//如果申请内存失败，则终结程序
	if (!L->elem) exit(OVERFLOW);

	//如果申请成功则初始化列表信息
	L->length = 0;
	L->listSize = LIST_INIT_SIZE;

	return OK;
} //InitList

//销毁线性表：销毁一个已经存在的线性表（默认传入的线性表是存在的）
Status DestroyList(struct ArrayList* L)
{
	//首先释放L->elem所指向的空间（该空间由malloc申请）
	free(L->elem);
	//free(L);//这里释放报错，不论是传入&L，L还是*L均不可，故不用单独释放L的内存
	L->length = 0;
	L->listSize = 0;
	return OK;
}//DestroyList

//将L重置为空表
Status ClearList(struct ArrayList* L)
{
	//先销毁线性表
	DestroyList(L);
	//再重新构建线性表
	InitList(L);
	return OK;
}//ClearList

//返回线性表中元素的个数
int ListLength(struct ArrayList* L)
{
	return	L->length;
}//ListLength


//判断线性表是否为空
Status ListEmpty(struct ArrayList* L)
{
	//如果实际数据长度为0则为空，否则不为空
	return ListLength(L) == 0;
}//ListEmpty

//用e返回L中的角标为i的元素（外面定义为实体，传入实体的地址，内部改变指向的内容而不改变地址）
Status GetElem(struct ArrayList* L, int i, struct Elem* e)
{
	//如果角标越界，则报警
	if (i >= ListLength(L)) return OVERFLOW;
	//否则将第i个元素取出，并将地址赋给指针
	*e = L->elem[i];
	return OK;
}//GetElem

//某种判定函数：这里例如判定元素是否相等
Status compare(struct Elem e1,struct Elem e2)
{
	return e1.number == e2.number;
}//compare

//返回L中第一个与e满足compare函数的角标，若不存在满足的元素，则返回-1
int LocateElem(struct ArrayList L, struct Elem e)
{
	//定义一个e2元素接收GetElem查找的结果
	struct Elem e2;
	for (int i = 0; i < ListLength(&L); i++)
	{
		//获取当前第i个元素放到e2中
		GetElem(&L, i, &e2);//如果e2被定义为指针这里切记不要再在e2上带寻址符
		//如果当前e2与传入的e满足compare函数则返回e2角标
		if (compare(e, e2))	return i;
	}

	//如果L中所有元素都不能与e满足compare函数则返回-1
	return -1;
}//LocateElem

//查找某一元素的直接前驱元素；若是第一元素，或传入元素不存在均报错
Status PriorElem(struct ArrayList L, struct Elem cur_e, struct Elem* pre_e)
{
	//查找cur_e在L中的位置，其中-1表示不存在
	int location = LocateElem(L, cur_e);
	//如果传入元素不存在，或传入元素位于第一位置（没有前驱）
	if (location < 1)
		//则报错
		return FALSE;
	//否则说明元素存在且具有前驱，获取其前驱
	GetElem(&L, location - 1, pre_e);
	return OK;
}//PriorElem

//查找某一元素的直接后继元素；若是末尾元素，或传入元素不存在均报错
Status NextElem(struct ArrayList L, struct Elem cur_e, struct Elem* next_e)
{
	int location = LocateElem(L, cur_e);
	if (location == -1 || location == ListLength(&L) - 1)
		return FALSE;
	GetElem(&L, location + 1, next_e);
	return OK;
}//NextElem

/*在线性表L角标为i的元素前插入新的元素
	插入情况：
	1.空表插入
		合法角标(i=0)
	2.半表插入
		合法角标(0<=i<=length)
		头部插入(i = 0)
		末尾插入(i = length)
		中间插入(0<=i<=length)
	3.满表插入（注意需要扩容）
		合法角标(0<=i<=length)
		头部插入(i = 0)
		末尾插入(i = length)
		中间插入(0<=i<=length)

	综上所述：
		角标范围：i>=0 && i<=length
		移动内容：原i及之后所有元素
		移动方式：从最后一个元素后移一位逐步前进到i后移一位为止
*/
Status ListInsert(struct ArrayList* L, int i, struct Elem* e)
{
	int length = ListLength(L);
	//判断插入元素角标位置是否合法
	if(i >= 0 && i <= length)
	{
		//将实际长度扩充
		L->length++;

		//如果增加后实际长度是否超出
		if (L->length > L->listSize)
		{
			//则扩充线性表长度
			//首先更新线性表新的长度
			L->listSize += LISTINCREMENT;
			struct Elem* mElem = (struct Elem*)realloc((L->elem),  L->listSize * sizeof(struct Elem));
			if(!mElem)
			{
				DestroyList(L);
				exit(OVERFLOW);
			}
			else
				L->elem = mElem;
			
		}//if (L->length > L->listSize)

		//通过循环将i及之后的所有元素后移一位(因为之前length++了，所以实际末尾角标应该为length-2)
		for (int j = L->length-2; j >= i; j--)
			L->elem[j+1] = L->elem[j];
		
		//循环完成后空出i位置，现将i位置插入新传入的元素
		L->elem[i] = *e;
	}//if(i >= 0 && i <= length)
	else exit(OVERFLOW);
	return OK;
}//ListInsert

//删除线性表L中角标为i的元素，并将被删除元素通过e传出
Status ListDelete(struct ArrayList* L, int i, struct Elem* e)
{
	//首先判断i是否合法
	int length = ListLength(L);
	if(i >= 0 && i < length)
	{
		//其次取出角标为i的元素(即：被删除元素)
		GetElem(L, i, e);

		//然后将i后面的元素前移一位
		for (int j = i+1; j <= L->length; j++)
			L->elem[j-1] = L->elem[j];

		L->length--;
	}//if(i >= 0 && i < length)
	else
		exit(OVERFLOW);
	
	return OK;
}//ListDelete

void PrintfInfo(struct ArrayList* L)
{
	for (int i = 0; i < L->listSize; i++)
	{
		printf("地址：%08X，数据：%d \n", &L->elem[i],L->elem[i].number);
	}
}//PrintfInfo

void TestInsert(struct ArrayList* L)
{

	struct Elem e;
	e.number = 77777;
	printf("测试空表插入\n");
	ListInsert(L,0,&e);
	//打印线性表的地址及数据，以确认是否是连续的空间
	PrintfInfo(L);

	e.number = 666666;
	printf("测试头部插入\n");
	ListInsert(L,0,&e);
	//打印线性表的地址及数据，以确认是否是连续的空间
	PrintfInfo(L);

	e.number = 999;
	printf("测试末尾插入\n");
	ListInsert(L,L->length,&e);
	//打印线性表的地址及数据，以确认是否是连续的空间
	PrintfInfo(L);

	e.number = 22;
	printf("测试中间插入\n");
	ListInsert(L,2,&e);
	//打印线性表的地址及数据，以确认是否是连续的空间
	PrintfInfo(L);

	printf("循环插满\n");
	for(int i = L->length;i<L->listSize;i++)
	{
		e.number = i;
		ListInsert(L,i,&e);
	}
	PrintfInfo(L);

	printf("满表末尾插入\n");
	e.number = 999999;
	ListInsert(L,L->length,&e);
	PrintfInfo(L);
}//TestInsert

void TestDelete(struct ArrayList* L)
{
	printf("删除前数据个数：%d\n",L->length);
	struct Elem e;
	//测试删除头部元素
	ListDelete(L,0,&e);
	printf("用于接收被删除元素的接收容器地址：%08X,值：%d，剩余数据个数：%d\n",&e,e.number,L->length);
	PrintfInfo(L);

	//测试删除尾部元素
	ListDelete(L,L->length-1,&e);
	printf("用于接收被删除元素的接收容器地址：%08X,值：%d，剩余数据个数：%d\n",&e,e.number,L->length);
	PrintfInfo(L);

	//测试删除中间元素
	ListDelete(L,3,&e);
	printf("用于接收被删除元素的接收容器地址：%08X,值：%d，剩余数据个数：%d\n",&e,e.number,L->length);
	PrintfInfo(L);

}//TestDelete

/******************************使用部分******************************/
int main()
{
	SetConsoleOutputCP(65001);

	/*
	 这里一开始定义成了指针出错。
	 定义为指针意味着需要在InitList函数内部为L申请空间，
	 不然L本身不存在，malloc得到的空间就无法赋值给L->elem（L并不存在）
	*/
	struct ArrayList L;	
	/*	调用函数构造一个空线性表
	 这里调用InitList传入的参数是&L的原因在于：
		上面部分定义L时，将其定义为了非指针的实体类型，
		而InitList函数头要求传入的是指针类型，所以加&取地址

		如果L是指针，调用L内部成员使用指向符号
		如果L是实体，调用L内部成员使用点符号
	*/
	//调用构造函数
	InitList(&L);

	//打印线性表的地址，以确认是否是连续的空间
	for (int i = 0; i < L.listSize; i++) printf("%08X\n",&L.elem[i]);
	
	//进行插入函数调用测试
	TestInsert(&L);

	//进行删除函数调用测试
	TestDelete(&L);

	char str[6];
	//调用判空函数
	ListEmpty(&L) ? printf("列表判定为：空\n") : printf("列表判定为：不空\n");

	//调用函数获取元素个数
	printf("当前元素个数：%d\n",ListLength(&L));

	struct Elem e;
	//测试获取角标为5的元素
	GetElem(&L,5,&e);


	//返回前驱测试
	PriorElem(L,e,&e);
	printf("获取到的前驱元素值为：%d\n",e.number);
	
	//返回后继测试
	NextElem(L,e,&e);
	printf("获取到的后继元素值为：%d\n",e.number);

	//重置测试
	ClearList(&L);
	printf("重置后元素个数：%d\n",ListLength(&L));


	printf("重置后，销毁前，线性表的首地址为：%08X\n",L.elem);
	//销毁测试
	DestroyList(&L);
	printf("销毁后，线性表的首地址为：%08X\n",L.elem);

	system("pause");
	return 0;
}  